# triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
triangle = [[-10]]
def minimumTotal(triangle):
    triangle_row=len(triangle)
    dp=[[0 for _ in range(len(triangle[triangle_row-1]))] for _ in range(triangle_row)]
    dp[0][0]=triangle[0][0]
    for i in range(1,triangle_row):
        triangle_col=len(triangle[i])
        for j in range(triangle_col):
            if j==0:
                #最左边的一列
                dp[i][j]=dp[i-1][j]+triangle[i][j]
            if j==triangle_col-1:
                #最右边的一列
                dp[i][j]=dp[i-1][j-1]+triangle[i][j]
            if j>0 and j<triangle_col-1:
                dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]
    print(min(dp[triangle_row-1]))
    print(dp)

#对空间复杂度进行优化
def minimumTotal1(triangle):
    triangle_row=len(triangle)
    dp=[0 for _ in range(int((triangle_row*triangle_row+triangle_row)/2))]
    # print(dp)
    dp[0]=triangle[0][0]
    for i in range(1, triangle_row):
        triangle_col = len(triangle[i])
        for j in range(triangle_col):
            if j==0:
                #最左边的一列
                # dp[i][j]=dp[i-1][j]+triangle[i][j]
                dp[int((i*i+i)/2+j)]=dp[int(((i-1)*(i-1)+i-1)/2+j)]+triangle[i][j]
            if j==triangle_col-1:
                #最右边的一列
                dp[int((i * i + i) / 2 + j)] = dp[int(((i - 1) * (i - 1) + i - 1) / 2 + j-1)] + triangle[i][j]
            if j>0 and j<triangle_col-1:
                # dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]
                dp[int((i * i + i) / 2 + j)] = min(dp[int(((i - 1) * (i - 1) + i - 1) / 2 + j - 1)],dp[int(((i-1)*(i-1)+i-1)/2+j)]) + triangle[i][j]
    return min(dp[int(((triangle_row-1)*(triangle_row-1)+triangle_row-1)/2):])
print(minimumTotal1(triangle))